package P164_最大间距;

/**
 * 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
 *
 * 如果数组元素个数小于 2，则返回 0。
 *
 * 示例1:
 *
 * 输入: [3,6,9,1]
 * 输出: 3
 * 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
 * 示例2:
 *
 * 输入: [10]
 * 输出: 0
 * 解释: 数组元素个数小于 2，因此返回 0。
 * 说明:
 *
 * 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
 * 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
 * 通过次数22,057提交次数39,339
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-gap
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

//根据要求，需要时 logN的排序算法，主要有桶排序（特殊化的计数排序）和基数排序
//这些都是需要消耗比较多空间的算法，桶排序经常用于大数据，可以用磁盘作为外部存储（所以桶排序也算是外部排序）

import java.util.*;

/**
 * 基数排序
 * 第一步
 * 以LSD为例，假设原来有一串数值如下所示：
 * 73, 22, 93, 43, 55, 14, 28, 65, 39, 81
 * 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
 * 0
 * 1 81
 * 2 22
 * 3 73 93 43
 * 4 14
 * 5 55 65
 * 6
 * 7
 * 8 28
 * 9 39
 * 第二步
 * 接下来将这些桶子中的数值重新串接起来，成为以下的数列：
 * 81, 22, 73, 93, 43, 14, 55, 65, 28, 39
 * 接着再进行一次分配，这次是根据十位数来分配：
 * 0
 * 1 14
 * 2 22 28
 * 3 39
 * 4 43
 * 5 55
 * 6 65
 * 7 73
 * 8 81
 * 9 93
 * 第三步
 * 接下来将这些桶子中的数值重新串接起来，成为以下的数列：
 * 14, 22, 28, 39, 43, 55, 65, 73, 81, 93
 * 这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
 * LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
 * 效率分析
 * 时间效率 [1]  ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
 * 实现方法
 * 最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
 * 最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
 * 实现原理
 * 基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
 * 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
 */
public class Solution {
    public int bucketSort(int[] nums){
        if(nums.length < 2){
            return 0;
        }
        // 1. 找最大值，确定分桶的大小
        // 2. 分桶
        // 3. 小桶里面排序（随便什么排序，因为数据已经很小，都近似于线性)
        // 4. 整合桶
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();
        //注意这里的桶大小，平均间距是 (max-min)/(len-1),取他的floor
        int bucketSize = (int)Math.floor((max - min)*1.0/nums.length + 1);
        if(bucketSize == 0){
            //全是相同的数
            return 0;
        }
        // 桶的个数是 nums.length + 1(想想 1,3,6,9  bucketSize 是2, 1在桶0,9在桶4，也就是总共需要5个桶）
        //分桶
        List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> inner = null;
        for(int i = 0;i<nums.length + 1;i++){
            buckets.add(new ArrayList<>());
        }
        for(int num : nums){
            int bucketIndex = (num - min)/bucketSize;
            inner = buckets.get(bucketIndex);
            if(inner == null){
                inner = new ArrayList<Integer>();
            }
            inner.add(num);
            buckets.set(bucketIndex, inner);
        }
        int count = 0;
        for(ArrayList<Integer> list : buckets){
            Collections.sort(list);
            for(Integer i : list){
                nums[count++] = i;
            }
        }

        max = 0;
        for(int i = 0;i<nums.length-1;i++){
            max = Math.max(nums[i + 1] - nums[i], max);
        }
        return max;
    }

    //基数排序
    public int baseSort(int[] nums){
        if(nums.length < 2){
            return 0;
        }
        int max = Arrays.stream(nums).max().getAsInt();
        int baseNum = (max+"").length();
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(10);
        for(int i = 0;i<10;i++){
            buckets.add(new ArrayList<>());
        }
        int curBaseBit = 0;
        int curBase;
        while(curBaseBit <= baseNum){
            curBase = (int)Math.pow(10, curBaseBit);
            curBaseBit ++;
            //1675 1675/10 = 167 167%10=7
            // 1675  1675/100 = 16 16%10 = 6
            //34  34/10 = 3 3%10 = 3
            for(int num : nums){
//                int tmp = num/curBase;
//                tmp = tmp%10;
                buckets.get((num/curBase)%10).add(num);
            }
            int count = 0;
            for(ArrayList<Integer> list : buckets){
                for(Integer n : list){
                    nums[count++] = n;
                }
                //别忘记重新初始化了
                list.clear();
            }
        }

        max = 0;
        for(int i = 0;i<nums.length-1;i++){
            max = Math.max(nums[i + 1] - nums[i], max);
        }
        return max;
    }

    public static void main(String args[]){
        int [] test = new int[]{1,1,1,2,2,2,3,3,4,5,88,45};
        System.out.println(new P164_最大间距.Solution().bucketSort(test));
        System.out.println(new P164_最大间距.Solution().baseSort(test));


    }

}
